class Solution {
    public void solveSudoku(char[][] board) {
        //回溯法的思想为，循环调用某个函数；
        backtrack(board);
    }
    public boolean backtrack(char[][] board){
        for(int i = 0 ; i < 9 ; i++){
            for (int j = 0 ; j < 9 ; j++){
                if(board[i][j] == '.'){
                    //填数
                    for(char k = '1'; k <= '9' ; k++){
                        if(isvalid(i,j,k,board)){
                            board[i][j] = k;
                            //为真的话，返回
                            if(backtrack(board)){
                                return true;
                            }
                            //为假的话，不匹配跳出，继续执行
                            board[i][j]='.';
                        }
                    }
                }else{
                    continue;
                }
                return false;
            }
        }
        return true;
    }


    //定义方法判断是否为真
    //当有重复元素的时候直接返回false
    public boolean isvalid(int row ,int col ,int val,char[][] board){
        //判断同一行有没有重复的元素
        for(int i = 0 ; i < 9; i++){
            if (board[row][i] == val){
                return false;
            }
        }
        //判断同一列有没有重复的元素
        for(int i = 0 ; i < 9 ; i++){
            if (board[i][col] == val){
                return false;
            }
        }
        //判断同一个小方格有没有重复的元素
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] == val){
                    return false;
                }
            }
        }
        return true;
    }
}